//
//  25. K个一组翻转链表.swift
//  Top600
//
//  Created by rjb on 2021/8/6.
//

import Foundation

class Solution25 {
    // 采用双指针
    // k个一组进行翻转，不足的不进行翻转
    func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        
        let vHead: ListNode = ListNode(-1)
        vHead.next = head
        var start = head
        var pre: ListNode? = vHead
        
        while start != nil {
            // 查看下一分组元素格式是否满足
            var end: ListNode? =  pre
            for _ in 0..<k {
                end = end?.next
                if end == nil {
                    return vHead.next
                }
            }
            // 下一组的开头
            let next = end?.next
            // 返回一组翻转
            let array = reverseSub(start: start!, end: end!)
            start = array[0]
            end = array[1]
            
            // 将链表重新接上
            pre?.next = start
            end?.next = next
            
            // 记录上一个分组结尾
            pre = end
            start = end?.next
        }
        return vHead.next
    }
    // 翻转开始的节点与尾部节点
    @discardableResult
    func reverseSub(start: ListNode, end: ListNode) -> [ListNode] {
        let endNext = end.next
        var pre: ListNode?
        var cur: ListNode? = start
        while cur != nil {
            let curnext = cur?.next
            cur?.next = pre
            pre = cur
            cur = curnext
            if cur === endNext {
                break
            }
        }
        // 返回头部与尾部
        return [end, start]
    }
    // K个一组反转链表
    // 分区, 反转链表
    
    func reverseKGroup2(_ head: ListNode?, _ k: Int) -> ListNode? {
        let vHead = ListNode(-1)
        vHead.next = head
        
        var pre: ListNode? = vHead
        var left = head
        var right = head
        while left != nil {
            // 查看是否满足
            for i in 0..<k {
                right = right?.next
                if right == nil {
                    return vHead.next
                }
            }
            // 记录下一个节点
            let next = right?.next
            // left 本是左边，right 本是右边
            reverseSub2(left: left, right: right)
            right?.next = nil
            // left 是右边了，right 是左边了
            // 链接起来
            pre?.next = right
            // 记录上一个节点
            pre = left
            left = next
            right = left
        }
        
        return vHead.next
    }
    // 在指定的链表里进行倒置
    func reverseSub2(left: ListNode?, right: ListNode?) {
        var pre: ListNode? = nil
        var cur: ListNode? = left
        while cur != nil {
            let next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }
    }
    static func test() {
        let solution = Solution25()
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        let node5 = ListNode(5)
        
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        let result = solution.reverseKGroup2(node1, 2)
        print(result)
    }
}
